{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decentralization Planning\n",
    "\n",
    "## Objective and Prerequisites\n",
    "\n",
    "Ready for a mathematical optimization modeling challenge? Put your skills to the test with this example, where you’ll learn how to model and solve a decentralization planning problem. You’ll have to figure out – given a set of departments of a company, and potential cities where these departments can be located – the “best” location for each department in order to maximize gross margins.\n",
    "\n",
    "This model is example 10 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 265 and 317-319.\n",
    "\n",
    "This modeling example is at the advanced level, where we assume that you know Python and the Gurobi Python API and that you have advanced knowledge of building mathematical optimization models. Typically, the objective function and/or constraints of these examples are complex or require advanced features of the Gurobi Python API.\n",
    "\n",
    "**Download the Repository** <br /> \n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "A large company wants to move some of its departments out of London. Doing so will result in reduced costs in some areas\n",
    "(such as cheaper housing, government incentives, easier recruitment, etc.), and increased costs in other areas (such as communication between departments). The cost implications for all possible locations of each department have been calculated.\n",
    "The goal is to determine where to locate each department in order to maximize the total difference between the reduced costs  from relocating and the increased communication costs between departments.\n",
    "\n",
    "The company comprises five departments (A, B, C, D and E). The possible cities for relocation are Bristol and Brighton, or a department may be kept in London. None of these cities (including London) may be the location for more than three of the departments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$d,d2 \\in \\text{Departments}=\\{A,B,C,D,E\\}$\n",
    "\n",
    "$c,c2 \\in \\text{Cities}=\\{\\text{Bristol}, \\text{Brighton}, \\text{London}\\}$\n",
    "\n",
    "### Parameters\n",
    "\n",
    "$\\text{benefit}_{d,c} \\in \\mathbb{R}^+$: Benefit -in thousands of dollars per year, derived from relocating department $d$  to city $c$.\n",
    "\n",
    "$\\text{communicationCost}_{d,c,d2,c2} \\in \\mathbb{R}^+$: Communication cost -in thousands of dollars per year, derived from relocating department $d$  to city $c$ and relocating department $d2$  to city $c2$.\n",
    "\n",
    "We define the set $dcd2c2 = \\{(d,c,d2,c2) \\in \\text{Departments} \\times \\text{Cities} \\times \\text{Departments} \\times \\text{Cities}: \\text{communicationCost}_{d,c,d2,c2} > 0  \\}$\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$\\text{locate}_{d,c} \\in \\{0,1 \\}$: This binary variable is equal 1, if department $d$  is located at city $c$, and 0 otherwise.\n",
    "\n",
    "$y_{d,c,d2,c2} = \\text{locate}_{d,c}*\\text{locate}_{d2,c2} \\in \\{0,1 \\}$: This auxiliary binary variable is equal 1, if department $d$ is located at city $c$ and department $d2$ is located at city $c2$, and 0 otherwise. \n",
    "\n",
    "\n",
    "### Constraints\n",
    "\n",
    "**Department location**: Each department must be located in only one city.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{c \\in \\text{Cities}} \\text{locate}_{d,c} = 1 \\quad \\forall d \\in \\text{Departments}\n",
    "\\end{equation}\n",
    "\n",
    "**Departments limit**: No city may be the location for more than three departments.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{d \\in \\text{Departments}} \\text{locate}_{d,c} \\leq 3 \\quad \\forall c \\in \\text{Cities}\n",
    "\\end{equation}\n",
    "\n",
    "**Logical Constraints**: \n",
    "\n",
    "- If $y_{d,c,d2,c2} = 1$ then $\\text{locate}_{d,c} = 1$ and $\\text{locate}_{d2,c2} = 1$.\n",
    "\n",
    "\\begin{equation}\n",
    "y_{d,c,d2,c2} \\leq \\text{locate}_{d,c} \\quad \\forall (d,c,d2,c2) \\in dcd2c2\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "y_{d,c,d2,c2} \\leq \\text{locate}_{d2,c2} \\quad \\forall (d,c,d2,c2) \\in dcd2c2\n",
    "\\end{equation}\n",
    "\n",
    "-  If $\\text{locate}_{d,c} = 1$ and $\\text{locate}_{d2,c2} = 1 $ then $y_{d,c,d2,c2} = 1$.\n",
    "\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{locate}_{d,c} + \\text{locate}_{d2,c2} - y_{d,c,d2,c2} \\leq 1 \\quad  \\forall (d,c,d2,c2) \\in dcd2c2\n",
    "\\end{equation}\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "**Gross margin**: Maximize the gross margin of relocation.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Maximize} \\quad Z = \\sum_{d \\in \\text{Departments}} \\sum_{c \\in \\text{Cities}} \\text{benefit}_{d,c}*\\text{locate}_{d,c} -\n",
    "\\sum_{d,c,d2,c2 \\in dcd2c2} \\text{communicationCost}_{d,c,d2,c2}*y_{d,c,d2,c2}\n",
    "\\end{equation}\n",
    "\n",
    "This linear integer programming formulation of the decentralization problem is in fact a linearization of a quadratic assignment formulation of this problem. With Gurobi 9.0, you can directly solve  the quadratic assignment formulation of the decentralization problem without the auxiliary variables and the logical constraints.\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "**Gross margin**: Maximize the gross margin of relocation.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Maximize} \\quad Z = \\sum_{d \\in \\text{Departments}} \\sum_{c \\in \\text{Cities}} \\text{benefit}_{d,c}*\\text{locate}_{d,c} -\n",
    "\\sum_{d,c,d2,c2 \\in dcd2c2} \\text{communicationCost}_{d,c,d2,c2}*\\text{locate}_{d,c}*\\text{locate}_{d2,c2}\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "**Department location**: Each department must be located in only one city.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{c \\in \\text{Cities}} \\text{locate}_{d,c} = 1 \\quad \\forall d \\in \\text{Departments}\n",
    "\\end{equation}\n",
    "\n",
    "**Departments limit**: No city may be the location for more than three departments.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{d \\in \\text{Departments}} \\text{locate}_{d,c} \\leq 3 \\quad \\forall c \\in \\text{Cities}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "We import the Gurobi Python Module and other Python libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Python 3.11 & Gurobi 11.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Input data  \n",
    "We define all the input data for the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lists of deparments and cities\n",
    "\n",
    "Deparments = ['A','B','C','D','E']\n",
    "Cities = ['Bristol', 'Brighton', 'London']\n",
    "\n",
    "# Create a dictionary to capture benefits -in thousands of dollars from relocation.\n",
    "\n",
    "d2c, benefit = gp.multidict({\n",
    "    ('A', 'Bristol'): 10,\n",
    "    ('A', 'Brighton'): 10,\n",
    "    ('A', 'London'): 0,\n",
    "    ('B', 'Bristol'): 15,\n",
    "    ('B', 'Brighton'): 20,\n",
    "    ('B', 'London'): 0,\n",
    "    ('C', 'Bristol'): 10,\n",
    "    ('C', 'Brighton'): 15,\n",
    "    ('C', 'London'): 0,\n",
    "    ('D', 'Bristol'): 20,\n",
    "    ('D', 'Brighton'): 15,\n",
    "    ('D', 'London'): 0,\n",
    "    ('E', 'Bristol'): 5,\n",
    "    ('E', 'Brighton'): 15,\n",
    "    ('E', 'London'): 0\n",
    "})\n",
    "\n",
    "# Create a dictionary to capture the communication costs -in thousands of dollars from relocation.\n",
    "\n",
    "dcd2c2, communicationCost = gp.multidict({\n",
    "    ('A','London','C','Bristol'): 13,\n",
    "    ('A','London','C','Brighton'): 9,\n",
    "    ('A','London','C','London'): 10,\n",
    "    ('A','London','D','Bristol'): 19.5,\n",
    "    ('A','London','D','Brighton'): 13.5,\n",
    "    ('A','London','D','London'): 15,\n",
    "    ('B','London','C','Bristol'): 18.2,\n",
    "    ('B','London','C','Brighton'): 12.6,\n",
    "    ('B','London','C','London'): 14,\n",
    "    ('B','London','D','Bristol'): 15.6,\n",
    "    ('B','London','D','Brighton'): 10.8,\n",
    "    ('B','London','D','London'): 12,\n",
    "    ('C','London','E','Bristol'): 26,\n",
    "    ('C','London','E','Brighton'): 18,\n",
    "    ('C','London','E','London'): 20,\n",
    "    ('D','London','E','Bristol'): 9.1,\n",
    "    ('D','London','E','Brighton'): 6.3,\n",
    "    ('D','London','E','London'): 7,\n",
    "    ('A','Bristol','C','Bristol'): 5,\n",
    "    ('A','Bristol','C','Brighton'): 14,\n",
    "    ('A','Bristol','C','London'): 13,\n",
    "    ('A','Bristol','D','Bristol'): 7.5,\n",
    "    ('A','Bristol','D','Brighton'): 21,\n",
    "    ('A','Bristol','D','London'): 19.5,\n",
    "    ('B','Bristol','C','Bristol'): 7,\n",
    "    ('B','Bristol','C','Brighton'): 19.6,\n",
    "    ('B','Bristol','C','London'): 18.2,\n",
    "    ('B','Bristol','D','Bristol'): 6,\n",
    "    ('B','Bristol','D','Brighton'): 16.8,\n",
    "    ('B','Bristol','D','London'): 15.6,\n",
    "    ('C','Bristol','E','Bristol'): 10,\n",
    "    ('C','Bristol','E','Brighton'): 28,\n",
    "    ('C','Bristol','E','London'): 26,\n",
    "    ('D','Bristol','E','Bristol'): 3.5,\n",
    "    ('D','Bristol','E','Brighton'): 9.8, \n",
    "    ('D','Bristol','E','London'): 9.1,\n",
    "    ('A','Brighton','C','Bristol'): 14,\n",
    "    ('A','Brighton','C','Brighton'): 5,\n",
    "    ('A','Brighton','C','London'): 9,\n",
    "    ('A','Brighton','D','Bristol'): 21,\n",
    "    ('A','Brighton','D','Brighton'): 7.5,\n",
    "    ('A','Brighton','D','London'): 13.5,\n",
    "    ('B','Brighton','C','Bristol'): 19.6,\n",
    "    ('B','Brighton','C','Brighton'): 7,\n",
    "    ('B','Brighton','C','London'): 12.6,\n",
    "    ('B','Brighton','D','Bristol'): 16.8,\n",
    "    ('B','Brighton','D','Brighton'): 6,\n",
    "    ('B','Brighton','D','London'): 10.8,\n",
    "    ('C','Brighton','E','Bristol'): 28,\n",
    "    ('C','Brighton','E','Brighton'): 10,\n",
    "    ('C','Brighton','E','London'): 18,\n",
    "    ('D','Brighton','E','Bristol'): 9.8,\n",
    "    ('D','Brighton','E','Brighton'): 3.5,\n",
    "    ('D','Brighton','E','London'): 6.3\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Deployment\n",
    "\n",
    "We create a model and the variables. These binary decision variables define the city at which each department will be located.\n",
    "\n",
    "Solving quadratic assignment problems  with Gurobi is as easy as configuring the global parameter `nonConvex`, and setting this parameter to the value of 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n",
      "Changed value of parameter nonConvex to 2\n",
      "   Prev: -1  Min: -1  Max: 2  Default: -1\n"
     ]
    }
   ],
   "source": [
    "model = gp.Model('decentralization')\n",
    "\n",
    "# Set global parameters \n",
    "model.params.nonConvex = 2\n",
    "\n",
    "# locate deparment d at city c\n",
    "locate = model.addVars(d2c, vtype=GRB.BINARY, name=\"locate\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each department must be located in exactly one city."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Department location constraint\n",
    "\n",
    "department_location = model.addConstrs((gp.quicksum(locate[d,c] for c in Cities) == 1 for d in Deparments), \n",
    "                                    name='department_location')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No city may be the location for more than three departments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Limit on number of departments\n",
    "\n",
    "departments_limit = model.addConstrs((gp.quicksum(locate[d,c] for d in Deparments) <= 3 for c in Cities), \n",
    "                                    name='departments_limit')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now set the optimization objective, which is to maximize gross margins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.setObjective((gp.quicksum(benefit[d,c]*locate[d,c] for d,c in d2c) \n",
    "                    - gp.quicksum(communicationCost[d,c,d2,c2]*locate[d,c]*locate[d2,c2] for d,c,d2,c2 in dcd2c2) ),\n",
    "                   GRB.MAXIMIZE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 8 rows, 15 columns and 30 nonzeros\n",
      "Model fingerprint: 0x2ad3c449\n",
      "Model has 54 quadratic objective terms\n",
      "Variable types: 0 continuous, 15 integer (15 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [5e+00, 2e+01]\n",
      "  QObjective range [7e+00, 6e+01]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 3e+00]\n",
      "Found heuristic solution: objective -73.9000000\n",
      "Presolve time: 0.00s\n",
      "Presolved: 62 rows, 69 columns, 192 nonzeros\n",
      "Variable types: 0 continuous, 69 integer (69 binary)\n",
      "\n",
      "Root relaxation: objective -6.750000e+01, 14 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0   67.50000    0   10  -73.90000   67.50000   191%     -    0s\n",
      "H    0     0                     -33.9000000   67.50000   299%     -    0s\n",
      "H    0     0                     -16.3000000   67.50000   514%     -    0s\n",
      "H    0     0                      14.9000000   67.50000   353%     -    0s\n",
      "     0     0   30.00000    0   22   14.90000   30.00000   101%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 3\n",
      "  MIR: 16\n",
      "  Zero half: 4\n",
      "  Mod-K: 2\n",
      "  RLT: 25\n",
      "\n",
      "Explored 1 nodes (43 simplex iterations) in 0.04 seconds\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 4: 14.9 -16.3 -33.9 -73.9 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.490000000000e+01, best bound 1.490000000000e+01, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# Verify model formulation\n",
    "\n",
    "model.write('decentralizationQA.lp')\n",
    "\n",
    "# Run optimization engine\n",
    "\n",
    "model.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "The optimal relocation plan and associated financial report follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Department</th>\n",
       "      <th>City</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>A</td>\n",
       "      <td>Bristol</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>D</td>\n",
       "      <td>Bristol</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>B</td>\n",
       "      <td>Brighton</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>C</td>\n",
       "      <td>Brighton</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>E</td>\n",
       "      <td>Brighton</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       " Department      City\n",
       "          A   Bristol\n",
       "          D   Bristol\n",
       "          B  Brighton\n",
       "          C  Brighton\n",
       "          E  Brighton"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "relocation_plan = pd.DataFrame(\n",
    "    {key for key, var in locate.items() if var.x > 0.5},\n",
    "    columns = [\"Department\", \"City\"],\n",
    ")\n",
    "relocation_plan.index=['']*len(relocation_plan)\n",
    "relocation_plan.sort_values([\"Department\", \"City\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "_________________________________________________________________________________\n",
      "Financial report\n",
      "_________________________________________________________________________________\n",
      "The yearly total benefit is $80,000.00 dollars\n",
      "The yearly total communication cost is $65,100.00 dollars\n",
      "The yearly total gross margin is $14,900.00 dollars\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n\\n_________________________________________________________________________________\")\n",
    "print(f\"Financial report\")\n",
    "print(\"_________________________________________________________________________________\")\n",
    "total_benefit = 0\n",
    "for c in Cities:\n",
    "    for d in Deparments:\n",
    "        if(locate[d,c].x > 0.5):\n",
    "            total_benefit += 1000*benefit[d,c]\n",
    "\n",
    "dollars_benefit = '${:,.2f}'.format(total_benefit)\n",
    "print(f\"The yearly total benefit is {dollars_benefit} dollars\")\n",
    "\n",
    "total_communication_cost = 0\n",
    "for d,c,d2,c2 in dcd2c2:\n",
    "    if(locate[d,c].x*locate[d2,c2].x > 0.5):\n",
    "        total_communication_cost += 1000*communicationCost[d,c,d2,c2]\n",
    "\n",
    "dollars_communication_cost = '${:,.2f}'.format(total_communication_cost)\n",
    "print(f\"The yearly total communication cost is {dollars_communication_cost} dollars\")\n",
    "\n",
    "total_gross_margin = total_benefit - total_communication_cost\n",
    "dollars_gross_margin = '${:,.2f}'.format(total_gross_margin)\n",
    "print(f\"The yearly total gross margin is {dollars_gross_margin} dollars\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "H. Paul Williams, Model Building in Mathematical Programming, fifth edition.\n",
    "\n",
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
